package letcode.oneQuestionPerDay._202004._24;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: 数组中的逆序对
 * @Date: 2020/4/24
 * @Author: 许群星
 */
public class ArrayReverseOrderTwo_a {
    public static void main(String[] args) {
        int[] nums={7,5,6,4};
        System.out.println(reversePairs(nums));
    }
    //提供方法        官方题解：归并排序
    public static int reversePairs(int[] nums) {
        int n=nums.length;

        if (n<2){
            return 0;
        }

        int[] copy=Arrays.copyOf(nums,n);

        int[] temp=new int[n];

        return mergeSort(copy,0,n-1,temp);
    }
    //合并排序
    private static int mergeSort(int[] nums,int left,int right,int[] temp){
        if (left==right) {
            return 0;
        }

        int mid=left+(right-left)/2;
        int leftNumbers=mergeSort(nums,left,mid,temp);
        int rightNumbers=mergeSort(nums,mid+1,right,temp);

        //如果有序，则无需合并
        if (nums[mid]<=nums[mid+1]){
            return leftNumbers+rightNumbers;
        }

        int crossNumbers=mergeAndCount(nums,left,mid,right,temp);
        return leftNumbers+rightNumbers+crossNumbers;
    }
    /**
     num[left,mid]和nums[mid+1,right]有序
     */
    private static int mergeAndCount(int[] nums,int left,int mid,int right,int[] temp){
        for (int i = left; i <=right ; i++) {
            temp[i]=nums[i];
        }
        int i=left;
        int j=mid+1;

        int count=0;
        for (int k = left; k <= right; k++) {
            //有下标访问，先判断是否越界
            if (i==mid+1){
                nums[k]=temp[j];
                j++;
            }else if (j==right+1){
                nums[k]=temp[i];
                i++;
            }else if (temp[i]<=temp[j]){
                nums[k]=temp[i];
                i++;
            }else {
                nums[k]=temp[j];
                j++;

                count+=(mid-i+1);
            }
        }
        return count;
    }
}
/*
面试题51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：

0 <= 数组长度 <= 50000
 */